package dp;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/dai-ma-sui-xiang-lu-121-mai-mai-gu-piao-odhle/
 * https://leetcode-cn.com/circle/article/qiAgHn/
 * 最亮眼的解法  省空间  都是把数组简化为常数复杂度
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/5xing-dai-ma-gao-ding-suo-you-gu-piao-ma-j6zo/
 * 3维数组的状态参数：
 * 用 i 表示第 i 天（i 的取值范围是 0 到 n - 1）；
 * 用 k 表示买卖次数； 之前卖出过一次k + 1
 * 这个状态用来针对这六道题的变化状态
 * 可以针对不同题来进行优化去掉
 * 用第三维的元素表示是否持有股票两种状态
 *
 *
 * 一维数组的参考：
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/188-mai-mai-gu-piao-de-zui-jia-shi-ji-iv-0ypq/
 *
 * TODO 重做   按照一维数组的方式
 */
public class TODO_买卖股票最佳时机_121_122_123_188_309_714 {

    public static void main(String[] args) {
        买卖股票最佳时机_121 m = new 买卖股票最佳时机_121();
        m.maxProfit(new int[]{7,1,5,3,6,4});
    }
}

/**
 * 只写dp的  可以有其他方式 见提交题解
 * 简化了最大卖出次数维度
 */
class 买卖股票最佳时机_121 {
    public int maxProfit(int prices[]) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for(int i = 1; i< len ;i++) {
            // 今天不持有股票 拥有的等值现金 等于  前一天就不持有  和前一天持有 今天卖了的最大值
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            // 今天持有股票 拥有的等值现金 等于  前一天就持有  和前一天不持有 今天买了的最大值
            // 带有前一天不持有最大值的是买无限次的     本题因为只能买卖一次  所以不存在 前一天不持有的最大值  该值肯定为0
            dp[i][1] = Math.max(dp[i-1][1], /* dp[i-1][0]*/ - prices[i]);
        }
        // 卖出股票肯定比持有多
        return dp[len - 1][0];
        // 以上只是dp[i][0] dp[i][1] 两个状态在循环轮转  可以把空间复杂度简化为O(1)
        /*int a = 0;
        int b = -prices[0];
        for(int i = 1; i< len ;i++) {
            // 今天不持有股票 拥有的等值现金 等于  前一天就不持有  和前一天持有 今天卖了的最大值
            a = Math.max(a, b + prices[i]);
            // 今天持有股票 拥有的等值现金 等于  前一天就持有  和前一天不持有 今天买了的最大值
            // 带有前一天不持有最大值的是买无限次的     本题因为只能买卖一次  所以不存在 前一天不持有的最大值  该值肯定为0
            b = Math.max(b, *//* dp[i-1][0]*//* - prices[i]);
        }
        return a;*/
    }

}


/**
 * 简化了最大卖出次数维度
 */
class 买卖股票最佳时机II_122 {
    public int maxProfit(int prices[]) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < len; i++) {
            // 今天不持有股票 拥有的等值现金 等于  前一天就不持有  和前一天持有 今天卖了的最大值
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            // 今天持有股票 拥有的等值现金 等于  前一天就持有  和前一天不持有 今天买了的最大值
            // 带有前一天不持有最大值的是买无限次的     本题因为可以存在 前一天不持有的最大值
            // TODO 注意这里和第一题的区别
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        // 卖出股票肯定比持有多
        return dp[len - 1][0];
        // 以上只是dp[i][0] dp[i][1] 两个状态在循环轮转  可以把空间复杂度简化为O(1)
        /*int a = 0;
        int b = -prices[0];
        for(int i = 1; i< len ;i++) {
            int tmp = a;
            // 今天不持有股票 拥有的等值现金 等于  前一天就不持有  和前一天持有 今天卖了的最大值
            a = Math.max(a, b + prices[i]);
            // 今天持有股票 拥有的等值现金 等于  前一天就持有  和前一天不持有 今天买了的最大值
            // 带有前一天不持有最大值的是买无限次的     本题因为只能买卖一次  所以不存在 前一天不持有的最大值  该值肯定为0
            b = Math.max(b, tmp - prices[i]);
        }
        return a;*/
    }


}
/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/tong-su-yi-dong-de-dong-tai-gui-hua-jie-fa-by-marc/
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/123-mai-mai-gu-piao-de-zui-jia-shi-ji-ii-s3xo/
 */
class 买卖股票最佳时机III_123 {
    public int maxProfit(int prices[]) {
        int len = prices.length;
        // 第二维是持有 不持有两种状态
        // 最多卖出2次  第三维是 2 + 1 = 3  可能是卖出过  0  1  2 三种状态
        long [][][] dp = new long[len][2][3];  // 用long 是因为有溢出
        // 第一天休息
        dp[0][0][0] = 0;
        // 第一天买入
        dp[0][1][0] = -prices[0];
        // 第一天卖出次数  不可能有的
        dp[0][0][1] = Integer.MIN_VALUE;
        dp[0][0][2] = Integer.MIN_VALUE;
        // 第一天持有并卖出 也是不可能
        dp[0][1][1] = Integer.MIN_VALUE;
        dp[0][1][2] = Integer.MIN_VALUE;

        for (int i = 1; i < len; i++) {
            // 在之前两个状态之间取max
            // 状态未持股 也从未卖出过 表示从没买过  资金等于0
            dp[i][0][0] = 0;
            //未持股，卖出过1次，可能是今天卖的，可能是之前卖的
            dp[i][0][1] = Math.max(dp[i-1][1][0] + prices[i], dp[i-1][0][1]);
            // 未持股，卖出过2次，可能是今天卖的，可能是之前卖的
            dp[i][0][2] = Math.max(dp[i-1][1][1] + prices[i], dp[i-1][0][2]);
            // 持股 卖出过0次 上次是买的    可能是之前买        可能是今天买
            dp[i][1][0] = Math.max(dp[i-1][0][0] - prices[i],dp[i-1][1][0]);
            // 持股 卖出过1次 上次是买的    可能是之前买        可能是今天买
            dp[i][1][1] = Math.max(dp[i-1][0][1]-prices[i],dp[i-1][1][1]);
            // 持股 卖出过2次 不可能
            dp[i][1][2] = Integer.MIN_VALUE;
        }
        // 看卖出一次  卖出两次  手上没股票时候的最大值
        int max = (int) Math.max(dp[len - 1][0][1], dp[len - 1][0][2]);
        return max > 0 ? max : 0;
        // 以上只是dp[i][0] dp[i][1] 两个状态在循环轮转  可以把空间复杂度简化为O(1)
        /*int buy1 = -prices[0];//第0天买入这天的股票的利润
        int sell1 = 0;//第0天买入这天的股票后又卖出的利润
        int buy2 = -prices[0];//第0天买入这天的股票又卖出，然后再买入的利润
        int sell2 = 0;//第0天买入这天的股票又卖出，然后再买入又卖出的利润
        for (int i = 1; i < len; ++i) {
            //第i天结束时的状态下，利润要么是第i-1天时的利润（第i-1天买入了，第i天啥也不干），要么是
            //第i天买入股票后的利润（第i-1天没有买入，第i天才买入）
            buy1 = Math.max(buy1, -prices[i]);
            //第i天结束时的状态下（此前肯定已经买入过一次了），利润要么是第i-1天时的利润
            //（第i-1天买入又卖出了，第i天啥也不干），要么是
            //第i天卖出股票后的利润（前面已经买入过一次，第i天卖出）
            sell1 = Math.max(sell1, buy1 + prices[i]);
            //第i天结束时的状态下，利润要么是第i-1天时的利润（此前已经买入卖出过一次，第i天啥也不干），
            //要么是第i天买入股票后的利润（此前买入卖出过一次，第i天再次买入）
            buy2 = Math.max(buy2, sell1 - prices[i]);
            //第i天结束时的状态下（此前肯定已经买入卖出过一次了），利润要么是第i-1天时的利润
            //（第i-1天第二次买入，第i天啥也不干），要么是
            //第i天卖出股票后的利润（前面已经买入过一次，第i天卖出）
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        //最大利润，根据表达式，最大利润要么是sell1要么是sell2，而sell1必然是小于等于sell2的
        return sell2;*/
    }
}

/**
 * 通过以上III_123的简化逻辑  可以简化为买 和卖两种操作  分别表示第i天买  第i天卖两种
 * TODO 重点跟着这个走一遍 股票系列
 *  https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/188-mai-mai-gu-piao-de-zui-jia-shi-ji-iv-0ypq/
 */
class 买卖股票最佳时机IV_188 {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        // 次数小于2 或者 k = 0 最大 0
        if(n < 2 || k == 0) return 0;
        // n天最多交易n/2次，如果k>n/2的话其实交易不了这么多次，所以 k = min(k, n//2)
        k = Math.min(k, n / 2);
        int[] dp = new int[2 * k + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        dp[1] = - prices[0];

        for(int i = 1; i < n; i++){
            for(int j = 1; j < 2 * k + 1; j++){
                if((j & 1) == 1){
                    dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);
                }else{
                    dp[j] = Math.max(dp[j], dp[j - 1] + prices[i]);
                }
            }
        }
        return dp[2 * k];

    }

}

class 买卖股票最佳时机_309{
    // TODO
}

class 买卖股票最佳时机_714{
    // TODO
}